// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-25 09:42
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.DeleteColumnsToMakeSorted;

import java.util.Arrays;

public class copyBigBull {
    // 贪心算法，记录需要保留的列数
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        String[] cur = new String[n];// 缓慢叠加列,用于保存不删除列的字符串数据
        int ans = 0;
        for (int i = 0; i < m; i++) {
            String[] cur2 = Arrays.copyOf(cur, n);
            for (int j = 0; j < n; j++) {
                cur2[j] += strs[j].charAt(i);// 判断字符串的第i个位置是否可以删除，使用cur2进行判断
            }
            if (isSorted(cur2)) {
                cur = cur2;
            } else {
                ans++;
            }
        }
        return ans;
    }

    // Use To Predicate That If Cur2 Is The Alphabetically
    private boolean isSorted(String[] cur2) {
        int n = cur2.length;
        for (int i = 1; i < n; i++) {
            if (cur2[i - 1].compareTo(cur2[i]) > 0) {
                return false;
            }
        }
        return true;
    }
}
